package ACWing.Dynamicprogramming.Backpack;
//2. 01背包问题

import java.util.Scanner;

/**
 * @author :chenjie
 * @date :Created 2022/11/10 22:15
 */
public class ZeroOne {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int V= sc.nextInt();
        int[]v=new int[N+1];//当前物体的体积
        int[]w=new int[N+1];//当前物体的价值
        for (int i = 0; i < N; i++) {
            v[i+1]=sc.nextInt();
            w[i+1]=sc.nextInt();
        }
        int[]dp=new int[V+1];//容量为j时前i个物体放入背包可以产生的最大容量
        dp[0]=0;
        for (int i = 1; i <N+1 ; i++) {
            for (int j = V; j>=v[i] ; j--) {

                    dp[j]=Math.max(dp[j],dp[j-v[i]]+w[i]);


            }
        }
        System.out.println(dp[V]);
    }

}
